using System;
using System.Collections.Generic;
using ClearSpringNet.Util;
using System.Linq;

namespace ClearSpringNet.Stream
{
    public class StreamSummary<T> : ITopK<T>
    {
        protected DoublyLinkedList<Counter<T>> counterList;

        protected int capacity;
        private Dictionary<T, ListNode2<Counter<T>>> counterMap;
        protected DoublyLinkedList<Bucket> bucketList;

        public class Bucket
        {
            public DoublyLinkedList<Counter<T>> counterList;
            public long count;

            public Bucket(long count)
            {
                this.count = count;
                counterList = new DoublyLinkedList<Counter<T>>();
            }
        }

        public StreamSummary(int capacity)
        {
            this.capacity = capacity;
            counterMap = new Dictionary<T, ListNode2<Counter<T>>>();
            bucketList = new DoublyLinkedList<Bucket>();
        }

        public int getCapacity() { return capacity; }

        public bool offer(T element)
        {
            return offerReturnAll(element).left;
        }

        public T offerReturnDropped(T item)
        {
            return offerReturnAll(item).right;
        }

        public Pair<Boolean, T> offerReturnAll(T item)
        {
            ListNode2<Counter<T>> counterNode = counterMap.Values.Where(x => x.getValue().Equals(item)).FirstOrDefault();
            var isNewItem = (counterNode == null);

            T droppedItem = default(T);
            if (isNewItem)
            {
                if (size() < capacity)
                {
                    var y = default(StreamSummary<T>); 
                    var x = new ListNode2<StreamSummary<T>>(y); 
                    // BucketList.Tail, item
                    // ListNode2<StreamSumary<T>> bucket
                    counterNode = bucketList.Enqueue(new Bucket(0)).getValue().counterList.Add(new Counter<T>(x, item));
                }
                else
                {
                    Bucket min = bucketList.first();
                    counterNode = min.counterList.Tail;
                    Counter<T> counter = counterNode.getValue();
                    droppedItem = counter.item;
                    counterMap.Remove(droppedItem);
                    counter.item = item;
                    counter.error = min.count;
                }
                counterMap.Add(item, counterNode);
            }
            incrementCounter(counterNode);
            return new Pair<bool, T>(isNewItem, droppedItem);
        }


        protected void incrementCounter(ListNode2<Counter<T>> counterNode)
        {
            Counter<T> counter = counterNode.getValue();       // count_i
            ListNode2<Bucket> bucketNode = counter.bucketNode;
            Bucket bucket = bucketNode.getValue();         // Let Bucket_i be the bucket of count_i
            ListNode2<Bucket> bucketNodeNext = bucketNode.getNext();
            Bucket bucketNext = bucketNodeNext == null ? null : bucketNodeNext.getValue(); // Let Bucket_i^+ be Bucket_i's neighbor of larger value
            bucket.counterList.Remove(counterNode);            // Detach count_i from Bucket_i's child-list
            counter.count++;                   // Increment count_i

            // Finding the right bucket for count_i
            if (bucketNext != null && counter.count == bucketNext.count)
            {
                bucketNext.counterList.Add(counterNode);       // Attach count_i to Bucket_i^+'s child-list
            }
            else // A new bucket has to be created
            {
                bucketNext = new Bucket(counter.count);        // Create a new Bucket Bucket_new
                // Assign Bucket_new the value of count_i
                bucketNext.counterList.Add(counterNode);       // Attach count_i to Bucket_new's child-list
                bucketNodeNext = bucketList.AddAfter(bucketNode, bucketNext);  // Insert Bucket_new after Bucket_i
            }

            counter.bucketNode = bucketNodeNext;

            //Cleaning up
            if (bucket.counterList.isEmpty())           // If Bucket_i's child-list is empty
            {
                bucketList.Remove(bucketNode);         // Detach Bucket_i from the Stream-Summary
            }
        }
        
        public int size()
        {
            return counterMap.Count;
        }

        public List<T> peek(int k)
        {
            throw new NotImplementedException();
        }
    }
}